"""
二分查找的递归实现
存在返回索引，不存在返回None
"""


def binary_search(sorted_s, value):
    if len(sorted_s) == 1:
        if sorted_s[0] == value:
            return 0
        else:
            return None
    index = len(sorted_s) // 2
    if sorted_s[index] == value:
        return index
    elif sorted_s[index] > value:
        return binary_search(sorted_s[:index], value)
    else:
        if len(sorted_s) <= 2:
            return None
        else:
            return index + binary_search(sorted_s[index + 1:], value)


s = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search(s, 2))
print(binary_search(s, -1))
